# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class BSTIterator:
    def __init__(self, root: TreeNode):
        self.lists = []
        if root:
            self.__search(root)
        self.lists.sort(reverse=True)

    def __search(self, root: TreeNode):
        if root.left:
            self.__search(root.left)
        self.lists.append(root.val)
        if root.right:
            self.__search(root.right)

    def next(self) -> int:
        """
        @return the next smallest number
        """
        return self.lists.pop(-1)

    def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        # return self.lists.__len__() == 0  # 好像还是这个快
        return bool(self.lists)
